package com.ken.algorithms.stack;

import java.util.Stack;

/**
 * <ul>
 * <li>Title: MainLC84</li>
 * <li>Description: TODO </li>
 * </ul>
 *
 * @author 程序员ken
 * @date 2021/5/19 0019 上午 9:25
 */
public class MainLC84 {

    /**
     * 【题目链接】：https://leetcode-cn.com/problems/largest-rectangle-in-histogram/
     * LeetCode：84. 柱状图中最大的矩形 — Hard
     * 【题目描述】：
     *
     * 给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。
     *
     * 求在该柱状图中，能够勾勒出来的矩形的最大面积。
    */
    public static void main(String[] args) {
        int[] arr ={14,71,63,248,73};
        System.out.println(largestRectangleArea(arr));
    }

/*
    //错误的原因  没有“找到”左右的边 如果单调递增 不会进入计算 (如果两者间隔为1，间距减1变为0，计算值永为0【此部分已修复】)
    public static int largestRectangleArea(int[] heights) {
        // 定义最终结果初始值为0
        Stack<Integer> stack = new Stack<Integer>();
        int res =0;

        for (int i = 0; i < heights.length; i++) {
            //
            while (!stack.isEmpty() && heights[stack.peek()]> heights[i]){
                int cur = stack.pop();
                int curMaxHeight =  heights[cur];//
                int leftSide = stack.isEmpty()?0:stack.peek();//左侧
                int rightSide =i;
                int spaceCount = rightSide-leftSide-1;
                curWidth  = spaceCount>0?spaceCount:1;
                res = Math.max(res,curMaxHeight*curWidth );
            }
            stack.push(i);//加入高度的索引
        }
        return res;
    }
 */


    public static int largestRectangleArea(int[] heights) {

        //左右边界加入‘0’
        int[] newHeights = new int[heights.length+2];
        newHeights[0] =0;
        newHeights[heights.length+1] =0;

        for (int i = 0; i < heights.length; i++) {
            newHeights[i+1] = heights[i];
        }

        // 定义最终结果初始值为0
        Stack<Integer> stack = new Stack<Integer>();
        int res =0;

        for (int i = 0; i < newHeights.length; i++) {
            // 如果栈不为空并且当前遍历到的矩形高度小于栈顶矩形的高度，
            // 则表示以当前栈顶矩形为高的矩形面积可以确定
            while (!stack.isEmpty() && newHeights[stack.peek()]> newHeights[i]){
                int cur = stack.pop();
                int curMaxHeight =  newHeights[cur];//获取当前最高的高度
                int leftSide = stack.peek();//左侧 cur-1;//
                int rightSide =i;
                int curWidth  = rightSide-leftSide-1;//间隔数
                res = Math.max(res,curMaxHeight*curWidth );
            }
            stack.push(i);//加入高度的索引
        }
        return res;
    }

}
